\documentclass{article}
\usepackage{xltxtra}
\usepackage{ctex}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{booktabs}

\makeatletter
\newcommand{\Rmnum}[1]{\expandafter\@slowromancap\romannumeral #1@}
\makeatother
\geometry{a4paper,top=1.5cm,bottom=1.5cm}

\title{Theoretical questions for Section 1}
\author{张皓祥 \\ 3200102536 强基数学2001}
\date{}

% main text
\begin{document}
\maketitle

% Question 1
\noindent \textbf{\Rmnum{1}. The linear interpolation of f}

\noindent \textbf{Sol.}

% Topic (a)
\noindent $\bullet \quad$ Since $f(x)=\frac{1}{x}$, $f''(x)=\frac{2}{x^3}$.
At the point $x_0=1,x_1=2$, we have $f(x_0)=1,f(x_1)=2$. Then the linear 
interpolation $p_1(f;x)$ satisfies
$$
p_1(f;x)-f(x_0)=\frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0) \quad \Longrightarrow
\quad p_1(f;x)=-\frac{1}{2}x-\frac{3}{2}
$$
Put all these formulas into the equation 
$f(x)-p_1(f;x)=\frac{f''(\xi (x))}{2}(x-x_0)(x-x_1)$, 
we have
\begin{gather*}
    \frac{(x-1)(x-2)}{2x}=\frac{(x-1)(x-2)}{(\xi(x))^3} \\
    \Longrightarrow \xi(x)=(2x)^{\frac{1}{3}}
\end{gather*} 

% Topic (b)
\noindent $\bullet \quad$ It's sufficient to find $\max \xi(x),\min\xi(x)$ 
and $\max f''(\xi(x))$ for $x\in \left[ 1,2 \right]$. 
Since $\xi(x)=(2x)^{\frac{1}{3}}$, which is increasing with $x$, then we have
\begin{gather*}
    \min\xi(x)=\xi(1)=2^{\frac{1}{3}} \\
    \max\xi(x)=\xi(2)=4^{\frac{1}{3}}=2^{\frac{2}{3}}
\end{gather*}
Since $f''(\xi(x))=\frac{1}{x}$ is decreasing with $x$, then 
$$
\max f''(\xi(x))=\max \frac{1}{x}=1 \quad \mbox{when} \quad x\in\left[1,2\right]
$$


\bigskip
% Question 2
\noindent \textbf{\Rmnum{2}. Find $p\in\mathbb{P}^+_{2n}$ such that $p(x_i)=f_i$}

\noindent \textbf{Sol.}

For $\forall k=0,1,2,\cdots,n$, define $l_k(x)$ as 
$$
l_k(x)=\prod ^n_{i=0,i\neq k}\frac{(x-x_i)^2}{(x_k-x_i)^2}
$$
Since $\frac{(x-x_i)^2}{(x_k-x_i)^2}\geq 0 \forall x\in\mathbb{R}$, we know
$l_k(x)\geq 0$. Besides, note that $\deg l_k(x)=2n$, $l_k\in\mathbb{P}^+_{2n}.$
By the definition, it's apparently that 
$l_k(x_k)=1$ and $l_k(x_i)=0\quad\forall i\neq k$.Then we define 
$$
p(x)=\sum_{i=0}^n f_i l_i(x) 
$$
For $\forall i=0,1,2,\cdots,n,\quad p(x_i)=\sum_{k=0}^n f_k l_k(x_i)=f_i l_i(x_i)=f_i.$
Since $f_i\geq 0$ and $l_k(x)\in\mathbb{P}^+_{2n}$, $p(x)\in\mathbb{P}^+_{2n}.$
So $p$ satisfies the question.

\bigskip
% Question 3
\noindent \textbf{\Rmnum{3}. Consider $f(x)=e^x$.}

\noindent \textbf{Sol.}

% Topic (a)
\noindent $\bullet \quad$ 
Choose $n=0$, $f\left[t\right]=f(t)=e^t=\frac{(e-1)^0}{0!}e^t$ is trival.

If for $n\geq 0$, we have proved that 
$f\left[t,t+1,\cdots,t+n\right]=\frac{(e-1)^n}{n!}e^t,\quad \forall t\in \mathbb{R}$, 
now we consider the case $n+1$.By assumption, for $\forall t\in \mathbb{R},$
\begin{gather*}
    f\left[t,t+1,\cdots,t+n\right] = \frac{(e-1)^n}{n!}e^t \\
    f\left[t+1,\cdots,t+n,t+(n+1)\right] = \frac{(e-1)^n}{n!}e^{t+1} 
\end{gather*}
Thus by Theorem 2.17, we get that
\begin{align*}
    f\left[t,t+1,\cdots,t+(n+1)\right] 
    & = \frac{f\left[t+1,\cdots,t+n,t+(n+1)\right]-f\left[t,t+1,\cdots,t+n\right]}{(t+(n+1)-t)} \\
    & = \frac{1}{n+1}\frac{(e-1)^n}{n!}e^t(e-1) \\
    & = \frac{(e-1)^{n+1}}{(n+1)!}e^t
\end{align*}
i.e. $n+1$ is also proved. By mathematical induction, the equation is proved.

% Topic (b)
\noindent $\bullet \quad$ 
Choose $t=0$, then $f\left[0,1,\cdots,n\right]=\frac{(e-1)^n}{n!}$. 
By Corollary 2.22, $f\left[0,1,\cdots,n\right]=\frac{1}{n!}f^{(n)}(\xi)$. 
Combine the two equations we have $f^{(n)}(\xi)=(e-1)^n$.

Since $f(x)=e^x$, differentiate it we have $f^{(n)}(x)=e^x$. Thus we get 
$e^{\xi}=(e-1)^n$. It implies that $\xi=\ln(e-1)^n=n\ln(e-1)$.
Considering that $\ln(e-1)\approx 0.5413248546129>\frac{1}{2},$ by calculation, 
$\xi$ is located to the right of the midpoint $\frac{n}{2}$.

\bigskip
% Question 4
\noindent \textbf{\Rmnum{4}. Newton formula}

\noindent \textbf{Sol.}

% Topic (a)
\noindent $\bullet \quad$ By Theorem 2.17 and the initial codition 
\begin{tabular}{c|cccc}
    $x$ & 0 & 1 & 3 & 4 \\
    \hline
    $f(x)$ & 5 & 3 & 5 & 12
\end{tabular}
we can compute the table of divided differences as followed:

\begin{center}
\begin{tabular}{c|cccc}
    0 & 5 & & & \\
    1 & 3 & -2 & & \\
    3 & 5 & 1 & 1 & \\
    4 & 12 & 7 & 2 & $\frac{1}{4}$
\end{tabular}    
\end{center}
Thus we can get
$$
p_3(f;x)=5-2x+x(x-1)+\frac{1}{4}x(x-1)(x-3)=\frac{1}{4}x^3-\frac{9}{4}x+5
$$

% Topic (b)
\noindent $\bullet \quad$ Use $p_3(f;x)$ to represente $f(x)$, make differentiation 
to $p_3$ we have $p_3'(X)=\frac{3}{4}x^2-\frac{9}{4}.$ Let $p_3'(x)=0,$ we get
$x_1=-\sqrt{3},x_2=\sqrt{3}.$ Choose $x_2=\sqrt{3}\in\left[1,3\right]$, when 
$1<x<x_2,p_3'(x)<0,p_3$ is decreasing. When $x>x_2,p_3'(x)>0,p_3$ is increasing. 
Thus $p_3$ will have a minimum at $x_2=\sqrt{3}$. By representation it implies 
that an approximate value for the location $x_{\min}$ for $f$ is $\sqrt{3}$.

\bigskip
% Question 5
\noindent \textbf{\Rmnum{5}. Consider $f(x)=x^7$.}

\noindent \textbf{Sol.}

% Topic (a)
\noindent $\bullet \quad$ Compute $f\left[0,1,1,1,2,2\right]$. Since $f(x)=x^7,$ 
we have $f'(x)=7x^6,f''(x)=42x^5$, then we have initial codition

\begin{center}
\begin{tabular}{c|ccc}
    $x$ & $f(x)$ & $f'(x)$ & $f''(x)$ \\
    \hline
    0 & 0 & & \\
    1 & 1 & 7 & 42 \\
    2 & 128 & 448 & 
\end{tabular}
\end{center}
Then by Corollary 2.36, 
$f\left[1,1\right]=f'(1)=7,f\left[1,1,1\right]=\frac{f''(1)}{2}=21,
f\left[2,2\right]=448$. The table of divided differences as followed:

\begin{center}
\begin{tabular}{c|cccccc}
    0 & 0 & & & & & \\
    1 & 1 & 1 & & & & \\
    1 & 1 & 7 & 6 & & & \\
    1 & 1 & 7 & 21 & 15 & & \\
    2 & 128 & 127 & 120 & 99 & 42 & \\
    2 & 128 & 448 & 321 & 201 & 102 & 30
\end{tabular}    
\end{center}
Thus $f\left[0,1,1,1,2,2\right]=30.$

% Topic (b)
\noindent $\bullet \quad$ By Newton formula, we have 
$\frac{f^{(5)(\xi)}}{5!}=f\left[0,1,1,1,2,2\right]=30$. 
Since $f^{(5)}(x)=\frac{7!}{2}x^2$, then $\frac{7!\xi^2}{2\times5!}=21\xi^2=30$. 
Considering $\xi\in\left(0,2\right),\xi=\sqrt{\frac{10}{7}}=\frac{\sqrt{70}}{7}$.

\bigskip
% Question 6
\noindent \textbf{\Rmnum{6}. Hermite interpolation}

\noindent \textbf{Sol.}

% Topic (a)
\noindent $\bullet \quad$ By initial condition, we have the table of divided 
differences as followed:
\begin{center}
\begin{tabular}{c|ccccc}
    0 & 1 & & & & \\
    1 & 2 & 1 & & & \\
    1 & 2 & -1 & -2 & & \\
    3 & 0 & -1 & 0 & $\frac{2}{3}$ & \\
    3 & 0 & 0 & $\frac{1}{2}$ & $\frac{1}{4}$ & -$\frac{5}{36}$
\end{tabular}
\end{center}
Then the polynomial of Hermite interpolation is 
$$
p(x)=1+x-2x(x-1)+\frac{2}{3}x(x-1)^2-\frac{5}{36}x(x-1)^2(x-3)
=\frac{1}{36}(x-4)(x-3)^2(5x+1)
$$
Thus $f(2)\approx p(2)=\frac{11}{18}$

% Topic (b)
\noindent $\bullet \quad$ By Theorem 2.37, we know that 
$\exists \xi\in\left(0,3\right)$ such that
$$
f(x)-p(x)=\frac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2
$$
Make difference to $y(x)=x(x-1)^2(x-3)^2$, we have 
$y'(x)=(x-3)(x-1)(5x^2-12x+3)$. Let $y'(x)=0$, we can find the root 
$x_1=1,x_2=3,x_3=\frac{1}{5}(6-\sqrt{21}),x_4=\frac{1}{5}(6+\sqrt{21})$. 
By analysis, $y(x)$ has maximal points at $x_3,x_4$. Calculate it, we can get 
$y(x_3)\approx 2.05944,y(x_4)\approx 1.074$. Thus the maximal error will be 
$\frac{f^{(5)}(\xi)}{5!}y(x)\leq \frac{M}{120}y(x_3)\approx 0.017162M$


\bigskip
% Question 7
\noindent \textbf{\Rmnum{7}. The forward difference and the backward difference.}

\noindent \textbf{Sol.}

\noindent $\bullet \quad$ Forward difference: let $f_i=f(x_i)$, by Theorem 2.29, 
$f\left[x_0,x_1,\cdots,x_k\right]=\frac{\Delta^kf(x)}{k!h^k}$. It's equivalent to 
$\Delta^kf(x)=k!h^kf\left[x_0,x_1,\cdots,x_n\right]$. 

\noindent $\bullet \quad$ Backward difference: by Theorem 2.27, we have 
$\Delta^kf_i=\nabla ^kf_{i+k}$, then by forward difference and Corollary 2.15,
let $f(x)=f_i$, $\nabla^kf(x)=\Delta^kf(x-k)
=k!h^kf\left[x_{-k},x_{-k+1},\cdots,x_{-1},x_0\right]
=k!h^kf\left[x_0,x_{-1},\cdots,x_{-k}\right].$

\bigskip
% Question 8
\noindent \textbf{\Rmnum{8}. partial difference}

\noindent \textbf{Sol.}

\noindent $\bullet \quad$ Use mathematical induction. Assume $x_i$ are all distinct.

$n=0$, $\frac{\partial}{\partial x_0}
f\left[x_0\right]=\lim\limits_{h\to 0}\frac{f[x_0+h]-f[x_0]}{h}
=\lim\limits_{h\to 0}\frac{f(x_0+h)-f(x_0)}{h}
=f'\left(x_0\right)=f\left[x_0,x_0\right]$ 
by Corollary 2.36.

If for $n-1\geq 0, \frac{\partial}{\partial x_0}f\left[x_0,x_1,\cdots,x_{n-1}\right]
=f\left[x_0,x_0,x_1,\cdots,x_{n-1}\right]$ is proved, now consider $n.$
First we have 
\begin{align*}
    & \frac{f\left[x_0+h,x_1,\cdots,x_n\right]-f\left[x_0,x_1,\cdots,x_n\right]}{h} \\
    = & \frac{\frac{f[x_1,\cdots,x_n]-f[x_0+h,\cdots,x_{n-1}]}{x_n-x_0-h} - 
        \frac{f[x_1,\cdots,x_n]-f[x_0,\cdots,x_{n-1}]}{x_n-x_0}}{h} \\
    = & \frac{(x_n-x_0)(f[x_0,\cdots,x_{n-1}]-f[x_0+h,\cdots,x_{n-1}]) + 
        h(f[x_1,\cdots,x_n]-f[x_0,\cdots,x_{n-1}])}{(x_n-x_0-h)(x_n-x_0)h} \\
    = & \frac{f[x_0,\cdots,x_{n-1}]-f[x_0+h,\cdots,x_{n-1}]}{(x_n-x_0-h)h} + 
        \frac{f[x_1,\cdots,x_n]-f[x_0,\cdots,x_{n-1}]}{(x_n-x_0-h)(x_n-x_0)} \\
    = & \frac{1}{x_n-x_0-h}\left(f[x_0,x_1,\cdots,x_n] - 
        \frac{f[x_0+h,\cdots,x_{n-1}]-f[x_0,\cdots,x_{n-1}]}{h}\right)
\end{align*}
By assumption, 
\begin{align*}
& \frac{\partial}{\partial x_0}f\left[x_0,x_1,\cdots,x_{n+1}\right] \\
= & \lim_{h\to 0} 
    \frac{f\left[x_0+h,x_1,\cdots,x_n\right]-f\left[x_0,x_1,\cdots,x_n\right]}{h} \\
= & \lim_{h\to 0}
    \frac{1}{x_n-x_0-h}\left(f[x_0,x_1,\cdots,x_n] - 
    \frac{f[x_0+h,\cdots,x_{n-1}]-f[x_0,\cdots,x_{n-1}]}{h}\right) \\
= & \frac{1}{x_n-x_0}\left(f[x_0,x_1,\cdots,x_n] - 
    \frac{\partial}{\partial x_0}f\left[x_0,x_1,\cdots,x_{n-1}\right]\right) \\
= & \frac{f[x_0,x_1,\cdots,x_n]-f[x_0,x_0,\cdots,x_{n-1}]}{x_n-x_0} \\
= & f\left[x_0,x_0,x_1,\cdots,x_n\right]
\end{align*}
Then by mathematical induction, the equation is proved.

\noindent $\bullet \quad$ For other partial derivative: $\forall i=0,1,\cdots,n$, 
since the divided difference does not depend on the numbering of the interpolation nodes, 
we have 
\begin{align*}
\frac{\partial}{\partial x_i}f\left[x_0,x_1,\cdots,x_n\right]
& = \frac{\partial}{\partial x_i}f\left[x_i,x_0,x_1\cdots,x_{i-1},x_{i+1},\cdots,x_n\right] \\
& = f\left[x_i,x_i,x_0,x_1\cdots,x_{i-1},x_{i+1},\cdots,x_n\right] \\
& = f\left[x_1,\cdots,x_i,x_i,\cdots,x_n\right]
\end{align*}
By induction, we can have
$$
\frac{\partial^{\sum_{i=0}^nk_i}}{\partial x_0^{k_0}\cdots\partial x_n^{k_n}}
f\left[x_0,x_1,\cdots,x_n\right] = 
f\left[\underbrace{x_0,\cdots,x_0}_{k_0+1},\cdots,\underbrace{x_n,\cdots,x_n}_{k_n+1}\right]
\quad \forall i=0,1,\cdots,n,k_i\in\mathbb{N}
$$

\bigskip
% Question 9
\noindent \textbf{\Rmnum{9}. A min-max problem.}

\noindent \textbf{Sol.}

Make a substition to $x$ as $t=\frac{2}{b-a}(x-\frac{a+b}{2})$, which is a linear 
transformation and change $a,b$ to -1,1. Then we also get $x=\frac{b-a}{2}t+\frac{a+b}{2}$. 
For any polynomial 
$$
p(x)=a_0x^n+a_1x^{n-1}+\cdots+a_n
$$
use the substition $x(t)$, we have 
\begin{align*}
p&=a_0(\frac{b-a}{2}t+\frac{a+b}{2})^n+a_1(\frac{b-a}{2}t+\frac{a+b}{2})^{n-1}+\cdots+a_n \\
&=a_0't^n+a_1't^{n-1}+\cdots+a_n'\quad t\in\left[-1,1\right]
\end{align*}
where $a_0'=a_0(\frac{b-a}{2})^n$. By substition and Corollary 2.47
\begin{align*}
    \min\max\limits_{x\in\left[a,b\right]} |a_0x^n+a_1x^{n-1}+\cdots+a_n|
    & = \min \max\limits_{t\in\left[-1,1\right]} |a_0't^n+a_1't^{n-1}+\cdots+a_n'| \\
    & = |a_0'|\min \max\limits_{t\in\left[-1,1\right]}|t^n+a_1''t^{n-1}+\cdots+a_n''| \\
    & = |a_0|(\frac{b-a}{2})^n\frac{1}{2^{n-1}} \\
    & = \frac{|a_0|(b-a)^n}{2^{2n-1}}
\end{align*}
where $a_i''=\frac{a_i'}{a_0'}$ and when it reaches the minimum, 
$t^n+a_1''t^{n-1}+\cdots+a_n''=\frac{1}{2^{n-1}}T_n(t)$.

\bigskip
% Question 10
\noindent \textbf{\Rmnum{10}. Imitate the proof of Chebyshev Theorem.}

\noindent \textbf{Sol.}

Since $\parallel T_n\parallel_{\infty} = 1$, and $T_n(a)\neq 0$ when $a>1$, 
we have $\parallel \hat{p}_n\parallel_{\infty}=\frac{\parallel T_n\parallel_{\infty}}
{|T_n(a)|}=\frac{1}{|T_n(a)|}$. Suppose the inequailty does not hold, then 
$\exists p\in\mathbb{P}^a_n,\parallel p\parallel_{\infty}<\frac{1}{|T_n(a)|}$. 
Define a polynomial of degree $n$ as $Q(x)=\hat{p}_n(x)-p(x)$. 
Let $x_k,k=0,1,\cdots,n$ be $n+1$ extremas of $T_n(x)$,
$$
Q'(x_k)=\hat{p}_n'(x_k)-p'(x_k)=\frac{1}{|T_n(a)|}|((-1)^k-|T_n(a)|p(x_k))
\quad \forall k=0,1,\cdots,n
$$
Thus $Q(x)$ has $n$ simple zeros in the domain $\left[-1,1\right]$. Besides, since both 
$\hat{p}_n,p\in\mathbb{P}^a_n,Q(a)=\hat{p}_n(a)-p(a)=1-1=0$, i.e. $a>1$ is also 1 zero.
Then $Q(x)$ has at least $n+1$ zeros, but the degree of it is no more than $n$, thus 
$Q(x)\equiv 0$, which implies $\parallel p\parallel_{\infty}=\frac{1}{|T_n(a)|}$. This 
is contradict to the assumption. Hence 
$\forall p\in\mathbb{P}^a_n,
\parallel \hat{p}_n\parallel_{\infty}\leq\parallel p\parallel_{\infty}$.

\bigskip
% Question 11
\noindent \textbf{\Rmnum{11}. Prove Lemma 2.50.}

\noindent \textbf{Sol.}

\noindent $\bullet \quad$ For $\forall t\in\left(0,1\right),t>0,1-t>0,
b_{n,k}(t)=\binom{n}{k} t^k(1-t)^{n-k}>0$.

\noindent $\bullet \quad$ By Binomial theorem, 
$\sum\limits_{k=0}^n b_{n,k}(t)=\sum\limits_{k=0}^n \binom{n}{k} t^k(1-t)^{n-k}
=\left[t+\left(1-t\right)\right]^n=q^n=1$.

\noindent $\bullet \quad$ For $k>0$, we have 
\begin{align*}
    kb_{n,k}(t) & = k\frac{n!}{k!(n-k)!}t^k(1-t)^{n-k} \\
    & = nt\frac{(n-1)!}{(k-1)![(n-1)-(k-1)]!}t^{k-1}(1-t)^{(n-1)-(k-1)} \\
    & = nt\binom{n-1}{k-1}t^{k-1}(1-t)^{(n-1)-(k-1)} \\
    & = b_{n-1,k-1}(t)
\end{align*}
Thus $\sum\limits_{k=0}^n kb_{n,k}(t)=\sum\limits_{k=1}^n ntb_{n-1,k-1}(t)
=nt\sum\limits_{k=0}^{n-1} b_{n-1,k-1}(t)=nt$.

\noindent $\bullet \quad$ For $\forall k>1$, we have
\begin{align*}
    k^2b_{n,k}(t)& = kntb_{n-1,k-1}(t) = nt(k-1)b_{n-1,k-1}(t)+ntb_{n-1,k-1}(t) \\
    & = n(n-1)t^2b_{n-2,k-2}(t)+ntb_{n-1,k-1}(t)
\end{align*}
Thus we have
\begin{align*}
    \sum\limits_{k=0}^n(k-nt)^2b_{n,k}(t)
    & = \sum\limits_{k=0}^nk^2b_{n,k}(t)-2nt\sum\limits_{k=0}^nb_{n,k}(t)
        +n^2t^2\sum\limits_{k=0}^n b_{n,k}(t) \\
    & = \sum\limits_{k=2}^n n(n-1)t^2b_{n-2,k-2}(t)
        + nt\sum\limits_{k=1}^nb_{n-1,k-1}(t) - 2nt\cdot nt + n^2t^2 \\
    & = (n^2-n)t^2+nt-n^2t^2 = nt(1-t).
\end{align*}

\end{document}